package leetcode.editor.cn.q1_300.q200;
//给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [3,2,3]
//输出：[3] 
//
// 示例 2： 
//
// 
//输入：nums = [1]
//输出：[1]
// 
//
// 示例 3： 
//
// 
//输入：nums = [1,2]
//输出：[1,2] 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 5 * 10⁴ 
// -10⁹ <= nums[i] <= 10⁹ 
// 
//
// 
//
// 进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。 
//
// 👍 675 👎 0

import java.util.ArrayList;
import java.util.List;

/**
 * 摩尔投票法
 * 看的官网
 */
public class Q229_MajorityElementIi {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<Integer> majorityElement(int[] nums) {
            // 要超过 1/3.最多有 2 个数能满足要求
            int element1 = 0;
            int element2 = 0;
            int vote1 = 0;
            int vote2 = 0;

            for (int num : nums) {
                if (vote1 > 0 && element1 == num) {
                    //第一个元素票数增加
                    vote1++;
                } else if (vote2 > 0 && element2 == num) {
                    //第二个元素票数增加
                    vote2++;
                } else if (vote1 == 0) {
                    // 选第一个元素
                    element1 = num;
                    vote1 = 1;
                } else if (vote2 == 0) {
                    // 选第二个元素
                    element2 = num;
                    vote2 = 1;
                } else {
                    // 三个元素，相互抵票
                    vote1--;
                    vote2--;
                }
            }

            // 最后再判断这两个元素是否合法
            int count1 = 0;
            int count2 = 0;
            for (int num : nums) {
                if (num == element1) {
                    count1++;
                }
                if (num == element2) {
                    count2++;
                }
            }

            List<Integer> ans = new ArrayList<>();
            if (vote1 > 0 && count1 > nums.length / 3) {
                ans.add(element1);
            }
            if (vote2 > 0 && count2 > nums.length / 3) {
                ans.add(element2);
            }

            return ans;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q229_MajorityElementIi().new Solution();
        // TO TEST
        System.out.println(solution.majorityElement(new int[]{3, 2, 3}));
        System.out.println(solution.majorityElement(new int[]{1}));
        System.out.println(solution.majorityElement(new int[]{1, 2}));
    }
}